package com.data_structure_algorithm.algorithm;

/**
 * @Authror PABLO
 * @Date 2022/4/7 15:11
 * @Desc 先后手纸牌
 */
public class HandCardsSuccessively {

    public static void main(String[] args) {

        int[] arr = {5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7};
        int i = win(arr);
        System.out.println(i);
    }

    private static int win(int[] arr) {

        return Math.max(xianhou(arr, 0, arr.length - 1), houshou(arr, 0, arr.length - 1));
    }

    private static int xianhou(int[] arr, int left, int right) {
        //如果当前只剩一张牌
        if (left == right) {
            return arr[left];
        }
        return Math.max( //这里max的原因是 先手在两种选择中，选择最大的
                //情况1 先手拿最左侧    //后手的范围houshou(arr, left + 1, right)
                (arr[left] + houshou(arr, left + 1, right)),
                //情况2 先手拿最右侧   //后手的范围，后手会返回给先手最小的
                (arr[right] + houshou(arr, left, right - 1)));

    }

    private static int houshou(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        return Math.min(//这里 min 代表，每次后手将最小的返回给先手，自己留大的
                (xianhou(arr, left + 1, right)),
                (xianhou(arr, left, right - 1)));
    }
}
